package LC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
 * Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
 */
public class LC_109_ConvertSortedListtoBinarySearchTree_LinkedList_BinaryTree {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);
        TreeNode root = Solution.sortedListToBST(head);
        List<List<Integer>> lists = levelOrder(root);
        System.out.println(lists);
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null)
            return resultList;
        List<Integer> levelStorage = new LinkedList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(null);
        while (queue.size() > 1) {
            TreeNode top = queue.poll();
            if (top == null) {
                resultList.add(levelStorage);
                queue.offer(null);
                levelStorage = new LinkedList<>();
            } else {
                levelStorage.add(top.val);
                if (top.left != null)
                    queue.offer(top.left);
                if (top.right != null)
                    queue.offer(top.right);
            }
        }
        resultList.add(levelStorage);
        return resultList;
    }

    static class Solution {
        static TreeNode sortedListToBST(ListNode head) {
            // 如果链表为空就直接返回null
            if (head == null) return null;

            // 链表只有一个结点
            if (head.next == null) return new TreeNode(head.val);

            // 快速移动结点，每次移动两个位置
            ListNode fast = head.next.next;
            // 记录中间结点
            ListNode mid = head;
            // 找中间结点
            while (fast != null && fast.next != null) {
                mid = mid.next;
                fast = fast.next.next;
            }

            // 以中间结点的下一个结点作为根结点
            TreeNode root = new TreeNode(mid.next.val);
            // 构建右子树
            root.right = sortedListToBST(mid.next.next);
            // 记录链表要断开的点
            ListNode midNext = mid.next;
            // 断开单链表（会破坏原来单链表的结构）
            mid.next = null;
            // 构建左子树
            root.left = sortedListToBST(head);
            // 重新将链表接好
            mid.next = midNext;
            // 返回结果
            return root;
        }
    }

}
